##########################
# 求最短路径
# @Author: MK
# @CreateDate: 2023/10/05
##########################
from AdjacencyList import Graph, Vertex
import PathPainter


# 将传入的二维数组转为用邻接表表示的图
def convertToGraph(graphList):
    listHeight = len(graphList)
    listWidth = len(graphList[0])
    tempGraph = Graph()
    key = 0
    for rowNum in range(0, listHeight):
        for colNum in range(0, listWidth):
            tempGraph.addVertex(key)
            key = key + 1
    for tempKey in range(0, key):
        vertX = tempKey % listWidth
        vertY = int(tempKey / listWidth)
        if vertX + 1 < listWidth:
            tempGraph.getVertex(tempKey).addNeighbor(tempKey + 1, graphList[vertY][vertX + 1])
        if vertY + 1 < listHeight:
            tempGraph.getVertex(tempKey).addNeighbor(tempKey + listWidth, graphList[vertY + 1][vertX])
        # if vertX - 1 >= 0:
        #     tempGraph.getVertex(tempKey).addNeighbor(tempKey - 1, graphList[vertY][vertX - 1])
        # if vertY - 1 >= 0:
        #     tempGraph.getVertex(tempKey).addNeighbor(tempKey - listWidth, graphList[vertY - 1][vertX])

    return tempGraph


# 传入二维数组，寻找从左上角到右下角的最短路径
def findPathFromLeftTopToRightDown(inputList=[]):
    graph = convertToGraph(inputList)
    # 因为这种图起点也有数值，所以额外加一个起点，把他连接到（0，0）点
    graph.addVertex('start')
    graph.getVertex('start').addNeighbor(0, inputList[0][0])
    graph.getVertex('start').distance = 0
    # 设置寻路起点、终点
    startVertexKey = 'start'
    endVertexKey = len(inputList) * len(inputList[0]) - 1
    # endVertexKey = 3
    # 打印一下这个图内所有的顶点编号
    print(graph.getVertices())
    # 打印一下这个图的邻接表
    for key in graph.getVertices():
        print(graph.getVertex(key))
    # 调用Graph中的findPath方法，寻找左上角到右下角的最短路径
    distance, path = graph.findPath(startVertexKey, endVertexKey)
    # 输出最终的结果
    print('-------------')
    print(path)
    print('Distance from', startVertexKey, 'to', endVertexKey, 'is', distance)

    PathPainter.drawPath(inputList, graph.getPathList(endVertexKey), distance)

    return distance


# Press the green button in the gutter to run the script.
if __name__ == '__main__':
    ga1 = [[1, 3, 1],
           [1, 5, 1],
           [4, 2, 1]]
    ga2 = [[2, 1, 6, 4],
           [5, 3, 1, 2],
           [3, 3, 4, 1],
           [4, 2, 3, 5]]
    ga3 = [[2, 1, 6],
           [5, 3, 1],
           [3, 3, 4],
           [4, 2, 3]]
    distance = findPathFromLeftTopToRightDown(ga1)


# loopCount = 0
# if __name__ == '__main__':
#     def Find(gArr=[[1, 3], [1, 5]], pointX=0, pointY=0):
#         globals()['loopCount'] = globals()['loopCount'] + 1
#         if pointX == 0 and pointY == 0:
#             return gArr[0][0]
#         if pointX == 0:
#             return Find(gArr, 0, pointY - 1) + gArr[pointY][pointX]
#         if pointY == 0:
#             return Find(gArr, pointX - 1, 0) + gArr[pointY][pointX]
#
#         upDistance = Find(gArr, pointX, pointY - 1)
#         leftDistance = Find(gArr, pointX - 1, pointY)
#         if upDistance < leftDistance:
#             return upDistance + gArr[pointY][pointX]
#         return leftDistance + gArr[pointY][pointX]
#
#
#     ga3 = [[1, 3, 1],
#            [1, 5, 1],
#            [4, 2, 1]]
#     ga4 = [[2, 1, 6, 4],
#            [5, 3, 1, 2],
#            [3, 3, 4, 1],
#            [4, 2, 3, 5]]
#     ga5 = [[2, 1, 6, 4, 1],
#            [5, 3, 1, 2, 2],
#            [3, 3, 4, 1, 3],
#            [4, 2, 3, 5, 4],
#            [4, 2, 3, 5, 5]]
#     ga6 = [[2, 1, 6, 4, 1, 4],
#            [5, 3, 1, 2, 2, 1],
#            [3, 3, 4, 1, 3, 7],
#            [4, 2, 3, 5, 4, 9],
#            [4, 2, 3, 5, 5, 1],
#            [4, 3, 7, 5, 5, 2]]
#     ga7 = [[2, 1, 6, 4, 1, 4, 3],
#            [5, 3, 1, 2, 2, 1, 6],
#            [3, 3, 4, 1, 3, 7, 4],
#            [4, 2, 3, 5, 4, 9, 2],
#            [4, 2, 3, 5, 5, 1, 7],
#            [4, 3, 7, 5, 5, 2, 3],
#            [4, 3, 7, 7, 5, 6, 3],
#            [4, 3, 7, 7, 5, 6, 3]]
#     ga8 = [[2, 1, 6, 4, 1, 4, 3, 1],
#            [5, 3, 1, 2, 2, 1, 6, 1],
#            [3, 3, 4, 1, 3, 7, 4, 1],
#            [4, 2, 3, 5, 4, 9, 2, 1],
#            [4, 2, 3, 5, 5, 1, 7, 1],
#            [4, 3, 7, 5, 5, 2, 3, 1],
#            [4, 3, 7, 7, 5, 6, 3, 1]]
#
#     # print(Find([[1, 3, 1], [1, 5, 1], [4, 2, 1]], 2, 2))
#     print(Find(ga7, 6, 7))
#     print(loopCount)
